class Solution {
public:
    int change(int amount, vector<int>& coins) {
      int len = coins.size();
      vector<int> dp(amount+1);
      dp[0] = 1;
      for(int i = 0;i < len;i++){
        for(int j = 1;j <= amount;j++){
            if(j >= coins[i]){
              dp[j] += dp[j-coins[i]];
            }
        }
      }
      return dp[amount];
    }
};
